//折半查找

#pragma once
//用折半查找方法，在有序数组a[n]中查找x
//若找到返回下标，否则返回-1
template <typename E>
int BinarySearch(E a[], int n, E x)
{
    int low = 0;
    int high = n - 1;
    while (low <= high)
    {
        //在a[low..high] 子序列中折半查找
        intmin = (low + high) / 2;
        if (x == [mid])
            return mid;
        else if (x < a[mid])
            high = mid - 1;
        else
            low = mid + 1;
    }
    return -1; // not found
}
//用折半查找方法(递归)，在有序序列a[Low. .high] 中查找x
//若找到返回下标，否则返回-1
template <typename E>
int BinarySearch(E a[], int Low, int high, E x)
{
    //当待查找序列a[Low..high] 为空时，找不到x
    if (Low > high)
        return -1;   //not found
    intmid = (Low + high) / 2;
    if (x == a[mid])
        return mid;
    else if (x < a[mid])
        return BinarySearch(a, Low, mid - 1, x);
    else
        return BinarySearch(a, mid + 1, high, x);
